<?php
/**
 * User: LRZ
 * Date: 2020/1/13
 * Time: 13:45
 */

/**
 *  167. 两数之和 II - 输入有序数组
 *
 *  标签：数组、双指针、二分查找
 *
 *  给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。
 *  函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。
 *
 *  说明:
 *      返回的下标值（index1 和 index2）不是从零开始的。
 *      你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。
 *
 *  示例:
 *      输入: numbers = [2, 7, 11, 15], target = 9
 *      输出: [1,2]
 *      解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
 *
 *  来源：力扣（LeetCode）
 *  链接：https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted
 *  著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

$start = microtime(true);

$numbers = [2, 7, 11, 15];
$target  = 9;
$res     = twoSum($numbers, $target);

$end = microtime(true);
print_r($res);
printf(' total run: %.2f s<br>' . 'memory usage: %.2f M<br> ', $end - $start, memory_get_usage() / 1024 / 1024);

function twoSum($numbers, $target)
{
    $l = 0;
    $r = count($numbers) - 1;
    while ($l < $r) {
        if ($numbers[$l] + $numbers[$r] === $target) {
            return [$l + 1, $r + 1];
        }

        if ($numbers[$l] + $numbers[$r] > $target) {
            $r--;
        } else {
            $l++;
        }
    }
    return [];
}